import java.io.File;
import java.io.PrintWriter;
import java.nio.file.Files;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
import java.util.stream.Collectors;

/**
 * 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
 * <p>
 * 请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
 * <p>
 * 你可以假设 nums1 和 nums2 不会同时为空。
 * <p>
 * 示例 1:
 * <p>
 * nums1 = [1, 3]
 * nums2 = [2]
 * <p>
 * 则中位数是 2.0
 * 示例 2:
 * <p>
 * nums1 = [1, 2]
 * nums2 = [3, 4]
 * <p>
 * 则中位数是 (2 + 3)/2 = 2.5
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author gongdeming
 * @create 2019-08-06
 */
public class FindMedianSortedArrays {
    /**
     * 采用二分法
     * <p>
     * n1 n2
     * n1 + n2 = half
     * nums[n2 - 1] <= nums[n1] < nums[n2]
     */
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 如果一个为空，计算返回
        if (nums1 == null || nums1.length == 0) {
            nums1 = nums2;
            nums2 = null;
        }
        if (nums2 == null || nums2.length == 0) {
            double mid = (nums1.length + 1) / 2. - 1;
            return (nums1[(int) Math.floor(mid)] + nums1[(int) Math.ceil(mid)]) / 2.;
        }
        // 如果两个数组是有序大小，计算返回
        if (nums2[nums2.length - 1] <= nums1[0]) {
            int[] tmp = nums1;
            nums1 = nums2;
            nums2 = tmp;
        }
        if (nums1[nums1.length - 1] <= nums2[0]) {
            double mid = (nums1.length + nums2.length + 1) / 2.;
            int left = (int) Math.floor(mid);
            int right = (int) Math.ceil(mid);
            if (left > nums1.length) {
                left = nums2[left - nums1.length - 1];
            } else {
                left = nums1[left - 1];
            }
            if (right > nums1.length) {
                right = nums2[right - nums1.length - 1];
            } else {
                right = nums1[right - 1];
            }
            return (left + right) / 2.;
        }

        // 如果两个数组有交叉，利用二分法计算
        return division(nums1, nums2);
    }


    @SuppressWarnings("all")
    public static double division(int[] nums1, int[] nums2) {
        int total = nums1.length + nums2.length;
        boolean isEven = total % 2 == 0;
        int half = isEven ? total / 2 - 1 : (total - 1) / 2; // 表示中位数左侧，应该有多少个数

        int s = 0;
        int e = total - 1;
        int mid = (s + e) / 2;

        int n1 = 0;  // n2 <= n1
        int n2 = 0;
        while (s <= e) {
            mid = (s + e) / 2;
            stack.add(mid);
            if (mid < nums1.length) {
                if (mid > half) {
                    // mid 偏右
                    e = mid - 1;
                    continue;
                }
                n1 = mid;
                n2 = half - mid;

                if (n2 > nums2.length - 1) {
                    if (n2 == nums2.length && nums2[nums2.length - 1] <= nums1[n1]) {
                        break;
                    }
                    else {
                        s = mid + 1;
                        continue;
                    }
                }
                if (nums1[n1] < nums2[n2]) {
                    if (n2 - 1 < 0 || nums2[n2 - 1] <= nums1[n1]) {
                        break;
                    } else {
                        s = mid + 1;
                        continue;
                    }
                }
                if (nums1[n1] > nums2[n2]) {
                    if (n1 - 1 < 0 || nums1[n1 - 1] <= nums2[n2]) {
                        mid = nums1.length + n2;
                        break;
                    } else {
                        e = mid - 1;
                        continue;
                    }
                }
                break;
            } else {
                if (mid - nums1.length > half) {
                    e = mid - 1;
                    continue;
                }
                n2 = mid - nums1.length;
                n1 = half - n2;
                if (n1 > nums1.length - 1) {
                    if (n1 == nums1.length && nums1[nums1.length - 1] <= nums2[n2]) {
                        break;
                    } else {
                        s = mid + 1;
                        continue;
                    }
                }
                if (nums1[n1] < nums2[n2]) {
                    if (n2 - 1 < 0 || nums2[n2 - 1] <= nums1[n1]) {
                        mid = n1;
                        break;
                    } else {
                        e = mid - 1;
                        continue;
                    }
                }
                if (nums1[n1] > nums2[n2]) {
                    if (n1 - 1 < 0 || nums1[n1 - 1] <= nums2[n2]) {
                        break;
                    } else {
                        s = mid + 1;
                        continue;
                    }
                }
                break;
            }
        }

        if (isEven) {
            int left = mid < nums1.length ? nums1[mid] : nums2[mid - nums1.length];

            Integer right = null;
            int nn1;
            int nn2;
            if (mid < nums1.length) {
                nn1 = mid;
                nn2 = half - mid;
                if (nn2 < nums2.length && nums2[nn2] >= left) {
                    right = nums2[nn2];
                }
                if (nn1 + 1 < nums1.length) {
                    right = right != null ? Math.min(right, nums1[nn1 + 1]) : nums1[nn1 + 1];
                }
            } else {
                nn2 = mid - nums1.length;
                nn1 = half - nn2;
                if (nn1 < nums1.length && nums1[nn1] >= left) {
                    right = nums1[nn1];
                }
                if (nn2 + 1 < nums2.length) {
                    right = right != null ? Math.min(right, nums2[nn2 + 1]) : nums2[nn2 + 1];
                }
            }
            return (left + right) / 2.;
        } else {
            return mid < nums1.length ? nums1[mid] : nums2[mid - nums1.length];
        }
    }

    public static void main(String[] args) {
        findMedianSortedArrays(new int[]{}, new int[]{1});
//        reTest();
//        randomTest();
    }

    private static List<Integer> stack = new ArrayList<>();

    public static void reTest() {
        File file = new File("F:\\tmp\\test.txt");
        try {
            List<String> strings = Files.readAllLines(file.toPath());
            if (strings.size() != 2) {
                throw new IllegalStateException();
            }
            String s1 = strings.get(0);
            String s2 = strings.get(1);
            int[] num1 = Arrays.stream(s1.replaceAll("[\\[\\] ]", "").split(","))
                    .mapToInt(Integer::valueOf)
                    .toArray();
            int[] num2 = Arrays.stream(s2.replaceAll("[\\[\\] ]", "").split(","))
                    .mapToInt(Integer::valueOf)
                    .toArray();
            test(num1, num2);
            System.out.println("测试通过!");
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    public static void randomTest() {
        int[] num1;
        int[] num2;
        Random random = new Random();
        int past = 0;
        final int max = 100;
        for (int i = 0; i < max; i++) {
            num1 = random.ints(1, 100).limit(random.nextInt(100) + 1).toArray();
            num2 = random.ints(1, 100).limit(random.nextInt(100) + 1).toArray();
            Arrays.sort(num1);
            Arrays.sort(num2);
            try {
                test(num1, num2);
            } catch (Exception e) {
                e.printStackTrace();
                try {
                    File file = new File("F:\\tmp\\test.txt");
                    try (PrintWriter printWriter = new PrintWriter(file)) {
                        printWriter.println(Arrays.toString(num1));
                        printWriter.println(Arrays.toString(num2));
                    }
                } catch (Exception e1) {
                    e1.printStackTrace();
                }

                System.out.println("past = " + past);
                System.out.println("Arrays.toString(num1) = " + Arrays.toString(num1));
                System.out.println("Arrays.toString(num2) = " + Arrays.toString(num2));
                break;
            }
            past++;
        }
        if (past == max) {
            System.out.println("测试通过!");
        }
    }

    public static void test(int[] arr1, int[] arr2) {
        stack.clear();

        double middle = findMedianSortedArrays(arr1, arr2);
        List<String> listMap = stack.stream()
                .map(i -> i < arr1.length ? "n1:" + arr1[i] : "n2:" + arr2[i - arr1.length])
                .collect(Collectors.toList());

        int[] all = new int[arr1.length + arr2.length];
        for (int i = 0; i < arr1.length; i++) {
            all[i] = arr1[i];
        }
        for (int j = 0; j < arr2.length; j++) {
            all[arr1.length + j] = arr2[j];
        }
        Arrays.sort(all);
        double middleExpect;
        if (all.length % 2 == 0) {
            middleExpect = (all[all.length / 2] + all[all.length / 2 - 1]) / 2.;
        } else {
            middleExpect = all[all.length / 2];
        }

        if (!(Math.abs(middle - middleExpect) < 0.000000001)) {
            String mes = String.format("arr1 = %s\narr2 = %s\nexpect = %s\nactual = %s", Arrays.toString(arr1), Arrays.toString(arr2), middleExpect, middle);
            throw new IllegalStateException(mes);
        }
    }
}
